package 简单算法;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-23
 * @Description: 给定一棵二叉查找树和一个新的树节点，将节点插入到树中。
 * 你需要保证该树仍然是一棵二叉查找树。
 * 样例
 * 样例  1:
 * 输入: tree = {}, node= 1
 * 输出: {1}
 * 样例解释:
 * 在空树中插入一个点，应该插入为根节点。
 * 样例 2:
 * 输入: tree = {2,1,4,3}, node = 6
 * 输出: {2,1,4,3,6}
 * 样例解释:
 * 如下：
 * 2             2
 * / \           / \
 * 1   4   -->   1   4
 * /             / \
 * 3             3   6
 * 挑战
 * 能否不使用递归？
 * 注意事项
 * 保证不会出现重复的值
 **/
public class 在二叉查找树中插入节点 {
    public static void main(String[] args) {
        在二叉查找树中插入节点 s = new 在二叉查找树中插入节点();
        TreeNode root = new TreeNode(2);
        TreeNode left = new TreeNode(1);
        root.left = left;
        TreeNode right = new TreeNode(4);
        root.right = right;
        TreeNode node1 = new TreeNode(3);
        left.left = node1;

        TreeNode node = new TreeNode(6);


        System.out.println(s.insertNode(root, node));
    }

    public TreeNode insertNode(TreeNode root, TreeNode node) {
        // write your code here
        if (root == null) {
            return node;
        }

        //先将二叉树拷贝一份
        TreeNode cur = root;
        //创建一个新的prev节点，用户当前的节点
        TreeNode prev = null;
        while (cur != null) {
            prev = cur;
            cur = cur.val > node.val ? cur.left : cur.right;
        }

        if (prev.val > node.val) {
            prev.left = node;
        } else {
            prev.right = node;
        }
        return root;
    }
}
